package com.masterlu.leetcode.daily.linkedlist.medium;

import com.masterlu.leetcode.daily.linkedlist.ListNode;

/**
 * 分割链表
 * https://leetcode-cn.com/problems/partition-list/
 *
 * @Author：masterlu
 * @Date：2021/4/10 5:33 下午
 */
public class M86Partition {


    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(4);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(2);

        partition(head, 3);
    }

    /**
     * 直接想到的，维护两个链表，一个存储小于x的数据，一个存储大于x的数据。最后将两个链表链接
     *
     * @param head
     * @param x
     * @return
     */
    public static ListNode partition(ListNode head, int x) {

        ListNode curr = head;
        ListNode smallHead = null;
        ListNode smallTail = smallHead;

        ListNode largeHead = null;
        ListNode largeTail = largeHead;

        while (curr != null) {
            //1.如果当前节点小于x，则断链，并存储在新链表上
            if (curr.val < x) {
                if (smallHead == null) {
                    smallHead = new ListNode(curr.val);
                    smallTail = smallHead;
                } else {
                    smallTail.next = new ListNode(curr.val);
                    smallTail = smallTail.next;
                }
            }else{
                if (largeHead == null) {
                    largeHead = new ListNode(curr.val);
                    largeTail = largeHead;
                } else {
                    largeTail.next = new ListNode(curr.val);
                    largeTail = largeTail.next;
                }
            }
            curr = curr.next;

        }

        //拼接两个链表返回
        if (null != smallHead) {
            smallTail.next = largeHead;
        } else {
            return largeHead;
        }

        return smallHead;
    }
}
